package codingPractice.huawei;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

/**
 * 每天早晨，环卫工人需要处理各个小区的生活垃圾，每个小区的生活垃圾由一队环卫工人负责运送到最近的垃圾回收站进行处理，
 * 求将所有小区垃圾送到垃圾回收站的最小距离和。
 * 假设小区和垃圾回收站都在都在一个m行 × n列的区域矩阵上，相邻点的距离为 1 ，
 * 只能上下左右移动；其中0表示垃圾处理站，1表示小区，2表示空白区域，-1表示障碍区域不可通行。
 * 区域内如果没有小区或者没有垃圾回收站，则最小距离和返回0。无法到达垃圾回收站的小区会单独处理，不计入本次距离和中。
 * 计算所有小区垃圾送到垃圾回收站的最小距离和。
 *
 * 输入
 * 第一行为两个数字 m 和 n，表示区域矩阵的行数和列数，中间使用空格分隔，m和n的范围均为 [1,300) 。
 * 接下来的 m 行表示一个 m*n 的区域矩阵数组，每行的元素间以空格分隔，其中元素取值仅为-1（障碍区域）、0（垃圾处理站）、1（小区）、2（空白区域）。
 *
 * 输出
 * 一个整数，表示所计算的最小距离和。
 *
 * BFS解答
 */
public class MinDistanceSum {

    private static final int[][] DIRECTIONS = {{0,1}, {1,0}, {0,-1}, {-1,0}};
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while(sc.hasNextInt()) {
            int m = sc.nextInt();
            int n = sc.nextInt();
            int[][] arr = new int[m][n];
            for(int i=0;i<m;i++) {
                for(int j=0;j<n;j++) {
                    arr[i][j] = sc.nextInt();
                }
            }

            int result = minDistance(arr);
            System.out.println(result);
        }
    }

    public static int minDistance(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;

        int[][] dist = new int[m][n];
        for(int[] row : dist) {
            Arrays.fill(row, Integer.MAX_VALUE);
        }

        //队列用于BFS搜索，初始化存放垃圾处理站的位置，而后存放未进行比较距离的坐标。
        Queue<int[]> queue = new LinkedList<>();

        for(int i=0;i<m;i++) {
            for(int j=0;j<n;j++) {
                //如果是垃圾站
                if (grid[i][j] == 0) {
                    queue.offer(new int[]{i, j});
                    dist[i][j] = 0;
                }
            }
        }

        //进行广度优先搜索
        while(!queue.isEmpty()) {
            int[] cur = queue.poll();
            int curX = cur[0], curY = cur[1];
            int curDist = dist[curX][curY];

            //扩展四个方向
            for(int[] dir : DIRECTIONS) {
                int newX = curX + dir[0];
                int newY = curY + dir[1];

                //检查是否越界或遇到障碍
                if(newX >= 0 && newX < m && newY >= 0 && newY < n && grid[newX][newY] != -1) {
                    if (curDist + 1 < dist[newX][newY]) {
                        dist[newX][newY] = curDist + 1;
                        queue.offer(new int[]{newX, newY});
                    }
                }
            }
        }

        //计算总距离
        int totalDistance = 0;
        boolean hasCommunity = false;

        for(int i=0;i<m;i++) {
            for(int j=0;j<n;j++) {
                if (grid[i][j] == 1) {
                    hasCommunity = true;
                    if (dist[i][j] == Integer.MAX_VALUE) {
                        //无法到达垃圾回收站的小区不计入距离
                        continue;

                    }
                    totalDistance += dist[i][j];
                }
            }
        }

        if (!hasCommunity) {
            return 0;
        }

        return totalDistance;
    }
}
